package com.zp.self.module.level_4_算法练习.数据结构.数组;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_36_有效的数独 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_36_有效的数独().isValidSudoku(
                new char[][]{{'5','3','.','.','7','.','.','.','.'}
                        ,{'6','8','.','1','9','5','.','.','.'}
                        ,{'.','9','8','.','.','.','.','6','.'}
                        ,{'8','.','.','.','6','.','.','.','3'}
                        ,{'4','.','.','8','.','3','.','.','1'}
                        ,{'7','.','.','.','2','.','.','.','6'}
                        ,{'.','6','.','.','.','.','2','8','.'}
                        ,{'.','.','.','4','1','9','.','.','5'}
                        ,{'.','.','.','.','8','.','.','7','9'}}
        ));
    }

    /**
    题目：请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
     数字 1-9 在每一行只能出现一次。
     数字 1-9 在每一列只能出现一次。
     数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

     注意：
     一个有效的数独（部分已被填充）不一定是可解的。
     只需要根据以上规则，验证已经填入的数字是否有效即可。
     空白格用 '.' 表示。

    分析：【perfect】
       1.三次遍历，通顺一点
           难点：9个小格的下标注意

    边界值 & 注意点：
       1.
     **/
    public boolean isValidSudoku(char[][] board) {
        //横向遍历
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            char[] chars = board[i];
            list.clear();
            for (char aChar : chars) {
                if (aChar == '.') continue;
                if (list.contains(aChar))
                    return false;
                else
                    list.add(aChar);
            }
        }
        //纵向遍历
        for (int i = 0; i < board.length; i++) {//列
            list.clear();
            for (int j = 0; j < board.length; j++) {//行
                if (board[j][i] == '.') continue;
                if (list.contains(board[j][i]))
                    return false;
                else
                    list.add(board[j][i]);
            }
        }
        //小9格子遍历
        int i=0,j=0;//起点  --终点: 6，6
        while (i<=6){
            j=0;
            while (j<=6){
                list.clear();
                for (int k = i; k < i+3; k++) {
                    char[] chars = board[k];
                    for (int l = j; l < j+3; l++) {
                        if (chars[l] == '.') continue;
                        if (list.contains(chars[l]))
                            return false;
                        else
                            list.add(chars[l]);
                    }
                }
                j+=3;
            }
            i+=3;
        }
        return  true;
    }
}
